package class10;

/**
 * https://leetcode.cn/problems/QC3q1f/
 * 前缀树，也叫字典树
 */
public class Code06_TrieTree {
    public static void main(String[] args) {
        String[] str = {"abc", "abd", "ace", "abd", "abd"};
        Trie1 trie1 = new Trie1();
        for (int i = 0; i < str.length; i++) {
            trie1.insert(str[i]);
        }

        System.out.println(trie1.root);

        int ace = trie1.search("ab");
        System.out.println(ace);

        int ab = trie1.prefixNumber("ab");
        System.out.println("ab = " + ab);

        trie1.delete("ace");
        System.out.println("trie1 = " + trie1);
    }

    private static class Trie1 {
        private Node root;

        public Trie1() {
            root = new Node();
        }

        public void delete(String key) {
            if (key == null || key.length() == 0) {
                return;
            }
            if (search(key) != 0) {
                char[] arr = key.toCharArray();
                Node cur = this.root;
                cur.pass--;
                for (int i = 0; i < arr.length; i++) {
                    int index = arr[i] - 'a';
                    if (--cur.nexts[index].pass == 0) {
                        cur.nexts[index] = null;
                        return;
                    }
                    cur = cur.nexts[index];
                }
                cur.end--;
            }
        }

        public int prefixNumber(String key) {
            if (key == null || key.length() == 0) {
                return 0;
            }
            char[] arr = key.toCharArray();
            Node cur = this.root;
            for (int i = 0; i < arr.length; i++) {
                int index = arr[i] - 'a';
                if (cur.nexts[index] == null) {
                    return 0;
                }
                cur = cur.nexts[index];
            }
            return cur.pass;

        }

        public void insert(String word) {
            if (word == null) return;
            char[] chars = word.toCharArray();
            Node node = root;
            node.pass++;
            int path = 0;
            for (int i = 0; i < chars.length; i++) {
                path = chars[i] - 'a';
                if (node.nexts[path] == null) {
                    node.nexts[path] = new Node();
                }
                node = node.nexts[path];
                node.pass++;
            }
            node.end++;
        }

        public int search(String key) {
            if (key == null) return 0;
            char[] chars = key.toCharArray();
            Node cur = this.root;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                if (cur.nexts[index] == null) {
                    return 0;
                }
                cur = cur.nexts[index];
            }
            return cur.end;
        }
    }

    private static class Node {
        public int pass;
        public int end;
        public Node[] nexts;

        public Node() {
            pass = 0;
            end = 0;
            nexts = new Node[26];
        }
    }

}




